import collections

# BFS
class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        p = collections.defaultdict(list)
        p_count = {}
        for item in prerequisites:
            p[item[0]].append(item[1])
            if item[0] not in p_count:
                p_count[item[0]] = 0
            if item[1] not in p_count:
                p_count[item[1]] = 1
            else:
                p_count[item[1]] += 1
        search_list = collections.deque()
        for key in p_count:
            if p_count[key] == 0:
                search_list.append(key)
        while search_list:
            k = search_list.popleft()
            for item in p[k]:
                p_count[item] -= 1
                if p_count[item] == 0:
                    search_list.append(item)
        for key in p_count:
            if p_count[key] > 0:
                return False
        return True

# DFS
# class Solution:
#     def canFinish(self, numCourses, prerequisites):
#         visited = [0] * numCourses
#         p = collections.defaultdict(list)
#         for item in prerequisites:
#             p[item[0]].append(item[1])
#             visited[item[0]] = 1
#
#         def dfs(i):
#             visited[i] = 2
#             for item in p[i]:
#                 if visited[item] == 2:
#                     return False
#                 else:
#                     if visited[item] == 1:
#                         flag = dfs(item)
#                         if not flag:
#                             return False
#             visited[i] = 0
#             return True
#
#         for i in range(numCourses):
#             if visited[i] != 0:
#                 flag = dfs(i)
#                 if not flag:
#                     return False
#
#         return True
data = Solution()
numCourses = 3
prerequisites = [[1, 0], [2, 0], [0, 2]]
print(data.canFinish(numCourses, prerequisites))
numCourses = 5
prerequisites = [[1,4],[2,4],[3,1],[3,2]]
print(data.canFinish(numCourses, prerequisites))
numCourses = 100
prerequisites = [[1,0],[2,0],[2,1],[3,1],[3,2],[4,2],[4,3],[5,3],[5,4],[6,4],[6,5],[7,5],[7,6],[8,6],[8,7],[9,7],[9,8],[10,8],[10,9],[11,9],[11,10],[12,10],[12,11],[13,11],[13,12],[14,12],[14,13],[15,13],[15,14],[16,14],[16,15],[17,15],[17,16],[18,16],[18,17],[19,17],[19,18],[20,18],[20,19],[21,19],[21,20],[22,20],[22,21],[23,21],[23,22],[24,22],[24,23],[25,23],[25,24],[26,24],[26,25],[27,25],[27,26],[28,26],[28,27],[29,27],[29,28],[30,28],[30,29],[31,29],[31,30],[32,30],[32,31],[33,31],[33,32],[34,32],[34,33],[35,33],[35,34],[36,34],[36,35],[37,35],[37,36],[38,36],[38,37],[39,37],[39,38],[40,38],[40,39],[41,39],[41,40],[42,40],[42,41],[43,41],[43,42],[44,42],[44,43],[45,43],[45,44],[46,44],[46,45],[47,45],[47,46],[48,46],[48,47],[49,47],[49,48],[50,48],[50,49],[51,49],[51,50],[52,50],[52,51],[53,51],[53,52],[54,52],[54,53],[55,53],[55,54],[56,54],[56,55],[57,55],[57,56],[58,56],[58,57],[59,57],[59,58],[60,58],[60,59],[61,59],[61,60],[62,60],[62,61],[63,61],[63,62],[64,62],[64,63],[65,63],[65,64],[66,64],[66,65],[67,65],[67,66],[68,66],[68,67],[69,67],[69,68],[70,68],[70,69],[71,69],[71,70],[72,70],[72,71],[73,71],[73,72],[74,72],[74,73],[75,73],[75,74],[76,74],[76,75],[77,75],[77,76],[78,76],[78,77],[79,77],[79,78],[80,78],[80,79],[81,79],[81,80],[82,80],[82,81],[83,81],[83,82],[84,82],[84,83],[85,83],[85,84],[86,84],[86,85],[87,85]]
print(data.canFinish(numCourses, prerequisites))
numCourses = 3
prerequisites = [[0,2],[1,2],[2,0]]
print(data.canFinish(numCourses, prerequisites))